package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 数组中出现次数超过一半的数字
 *
 * @author yuhushuan
 * @date 2020/6/24 21:28
 */
public class _39_1_MoreThanHalfNumber {

    /**
     * 书中解法
     *
     * @param array
     * @return
     */
    private static Integer moreThanHalfNumber(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        int mid = array.length >> 1;
        int start = 0;
        int end = array.length - 1;
        int index = partition(array, start, end);
        while (index != mid) {
            if (index < mid) {// 中位数在右
                start = index + 1;
                index = partition(array, start, end);
            } else {// 中位数在左
                end = index - 1;
                index = partition(array, start, end);
            }
        }
        int result = array[mid];
        if (!checkMoreThanHalf(array, result)) {
            return null;
        }
        return result;
    }

    private static boolean checkMoreThanHalf(int[] array, int result) {
        int times = 0;
        for (int v : array) {
            if (v == result) {
                times++;
            }
        }
        return times > (array.length >> 1);
    }

    /**
     * 快速排序算法——partition
     *
     * @param array
     * @param start
     * @param end
     * @return
     */

    private static int partition(int[] array, int start, int end) {
        if (array == null || start < 0 || end < start){
            throw new IllegalArgumentException("Invalid Argument");
        }
        int index = (int) (start + Math.random() * (end - start + 1));
        swap(array, index, end);// 基准位于末尾

        int small = start - 1;
        for (int i = start; i <= end; i++)
            if (array[i] <= array[end]) {
                small++;
                if (i > small) {
                    swap(array, i, small);
                }
            }
        return small;
    }

    /**
     * 交换数组内两个元素
     *
     * @param array
     * @param i
     * @param j
     */

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static Integer moreThanHalfNumber_solution2(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        int result = array[0];
        int times = 0;

        for (int value : array) {
            if (times == 0) {
                result = value;
                times = 1;
            } else if (result == value) {
                times++;
            } else {
                times--;
            }
        }
        if (!checkMoreThanHalf(array, result)) {
            return null;
        }
        return result;
    }

    public static void main(String[] args) {
        // 功能测试
        // 存在
        print(new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2});
        print(new int[]{1, 2});
        // 不存在
        print(new int[]{1, 2, 3, 2, 4, 5, 5, 4, 2});

        // 特殊输入测试
        print(new int[]{1});
        print(null);
    }

    private static void print(int[] array) {
        System.out.println("数组：");
        System.out.println(Arrays.toString(array));
        System.out.println("存在出现超过数组长度一半的数字为-解法1：" + moreThanHalfNumber(array));
        System.out.println("存在出现超过数组长度一半的数字为-解法2：" + moreThanHalfNumber_solution2(array));
        System.out.println();
    }
}
